题解 CF746G New Roads

发表于 | 更新于

题意：给你$3$个数字$n,t,k;$分别表示一棵树有$n$个点; 这棵树的深度$t$,以及叶子节点的个数$k;$给你树的每层节点个数; 让你画出这么一棵树; 输出它的$n-1$条边;

首先计算这样的树最多与最少能有几个叶子节点，如果$k$不在这个范围内，则输出$-1,return 0;$

然后我们钦定同一深度的点都指向同一个父亲 这样叶子节点最多，并且计算一下我们需要消除的叶子节点数量$=n-t-k$。

然后从下到上进行调整,每次将当前层节点指向的父亲转移成上一层每个节点(如果当前层节点数大于上一层节点数，则多余的挤在一起)枚举用两个指针，一个指针指向当前层，另一个指针指向上一层，同时$+1$，如果一个指针指向了尽头就跳到上一层，如果消除的叶子节点数$=$我们需要消除的叶子节点数量则退出。

然后输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int a[300000],mx,mn,tot;
int main(){
    int n=read(),t=read(),k=read();
    for (int i=1;i<=t;++i){
        a[i]=read();
        if (a[i]>a[i-1])mn+=a[i]-a[i-1];
    } 
    mx=n-t;
    if (k<mn||k>mx){
        cout<<-1;return 0;
    }
    printf("%d\n",n);
    for (int i=2;i<=a[1]+1;++i)printf("1 %d\n",i);//根节点与其子节点特殊处理
    int T=mx-k;tot=a[1]+2;//T为我们需要消除的叶子节点数量，tot为初始指针指向第三层的第一个节点
    for (int i=2;i<=t;++i){
        int p=min(a[i],a[i-1]),q=0;//p表示当前层可以消除的叶子节点数，q是指针
        while (p&&T){
            if (q)--T;//第一个点是下一层多余节点的连接处，所以T不能--;
            --p;
                    printf("%d %d\n",tot+q-a[i-1],tot+q);
            ++q;
        }
        while (q<a[i]){
            printf("%d %d\n",tot-a[i-1],tot+q);
            ++q;
        }//处理多余节点
        tot+=a[i];//指针指向下一行
    }
}